package ThirdWeek;

public class Monday {
    // 1576、替换所有的问号
    public String modifyString(String s) {
        char[] ss = s.toCharArray();
        int n = s.length();
        for (int i = 0;i < n;i++) {
            if (ss[i] == '?') {
                // 替换
                for (char ch = 'a';ch <= 'z';ch++) {
                    // ? 在开头或者结尾的时候要进行特殊处理，在开头只判断前一位，在结尾只判断后一位
                    if ((i == 0 || ch != ss[i -1]) && (i == n - 1 || ch != ss[i + 1])) {
                        ss[i] = ch;
                        break;
                    }
                }
            }
        }
        return String.valueOf(ss);
    }


    // 面试题17.19.消失的两个数字
    public int[] missingTwo(int[] nums) {
        // 先对其中的所有数据都进行异或操作
        int tmp = 0;
        for (int num : nums) {
            tmp ^= num;
        }
        // 丢失两个数字，就是在其原来数组的长度的基础上加2
        // 这个是根究下标1开始按照顺序的
        for (int i = 1;i <= nums.length + 2;i++) {
            tmp ^= i;
        }
        // 这个时候tmp就是丢失的两个数字的异或结果了
        // 我们找其最右面的第一个为1的比特位的位置，这就说明两个数字比特位第一次不同的地方，就可以根究这个比特位是0或1
        // 把nums和1-nums.length + 2下标的值分成两份，进行异或，每一份最终的结果就是丢失的数据
        int[] ret = new int[2];
        int k = (tmp == Integer.MIN_VALUE ? tmp : tmp & (-tmp));
        for (int num : nums) {
            if ((num & k) != 0) {
                //对应的比特位不为0
                ret[0] ^= num;
            }else {
                //对应的比特位为0
                ret[1] ^= num;
            }
        }
        for(int i = 1;i <= nums.length + 2;i++) {
            if ((i & k) != 0) {
                ret[0] ^= i;
            }else {
                ret[1] ^= i;
            }
        }
        return ret;
    }

    // 137、只出现一次的数字II
    public int singleNumber(int[] nums) {
        // 这些数字都是32比特位的整数
        // 我们对于每一个比特位进行计数，当是1的时候进行sum++，每次的比特位计数结束后对其sum进行%3操作，因为出现的是3次重复
        // 如果sum最后为1的话，那么这个比特位对应的1就是我们要的数字其中的一个比特位，对其进行32次处理就可以得出结果
        int ret = 0;
        for (int i = 0;i < 32;i++) {
            int sum = 0;
            for (int num : nums) {
                if (((num >> i) & 1) == 1) {
                    sum++;
                }
            }
            sum %= 3;
            if (sum == 1) {
                //这个比特位是返回的数字的比特位
                ret |= (sum << i);
            }
        }
        return ret;
    }
}
